Search for: All records

In a sweep cover problem, mobile sensors move around to collect information from positions of interest (PoIs) periodically and timely. A PoI is sweep-covered if it is visited at least once in every time period t. In this paper, we study approximation algorithms on three types of sweep cover problems. The partial sweep cover problem (PSC) aims to use the minimum number of mobile sensors to sweep-cover at least a given number of PoIs. The prize-collecting sweep cover problem aims to minimize the cost of mobile sensors plus the penalties on those PoIs that are not sweep-covered. The budgeted sweep cover problem (BSC) aims to use a budgeted number N of mobile sensors to sweep-cover as many PoIs as possible. We propose a unified approach which can yield approximation algorithms for PSC and PCSC within approximation ratio at most 8, and a bicriteria (4, 1 2 )-approximation algorithm for BSC (that is, no more than 4N mobile sensors are used to sweep-cover at least 1 2 opt PoIs, where opt is the number of PoIs that can be sweep-covered by an optimal solution). Furthermore, our results for PSC and BSC can be extended to their weighted version, and our algorithm for PCSC answers a question proposed in Liang etal. (Theor Comput Sci, 2022) on PCSC 

Abstract Migratory divides are proposed to be catalysts for speciation across a diversity of taxa. However, it is difficult to test the relative contributions of migratory behaviour vs. other divergent traits to reproductive isolation. Comparing hybrid zones with and without migratory divides offers a rare opportunity to directly examine the contribution of divergent migratory behaviour to reproductive barriers. We show that across replicate sampling transects of two pairs of barn swallow (Hirundo rustica) subspecies, strong reproductive isolation coincided with a migratory divide spanning 20 degrees of latitude. A third subspecies pair exhibited no evidence for a migratory divide and hybridised extensively. Within migratory divides, overwintering habitats were associated with assortative mating, implicating a central contribution of divergent migratory behaviour to reproductive barriers. The remarkable geographic coincidence between migratory divides and genetic breaks supports a long‐standing hypothesis that the Tibetan Plateau is a substantial barrier contributing to the diversity of Siberian avifauna.